package org.shj.algorithm.string;

/**
 * 字符串循环左移问题
 *   假设有一个字符串 abcdef, 左移两位后是 cdefab，
 *   要求时间复杂度为 O(n)， 空间复杂度为 O(1)
 *   注： 循环左移 k 位，等于循环右移 n-k 位
 *
 *   思路：
 *   用 X 表示字符串的前 k 位， Y 表示后面的字符串
 *   X' 表示字符串 X 的反转。
 *   则 (X'Y')' = YX
 *   如： X=ab, Y=cdef
 *   则： X'=ba,  Y'=fedc
 *       X'Y'=bafedc  -->  (X'Y')'=cdefab=YX
 *
 * @author Shen Huang Jian
 * @date 2019-03-23 9:04
 */
public class LoopLeftMove {

    public static void main(String[] args){
        String[] arr = {"a", "b", "c", "d", "e", "f"};
        String[] arr2 = {"a", "b", "c", "d", "e", "f"};
        leftMove(arr, 2);
        leftMove(arr2, 8);
    }

    public static void leftMove(String[] arr, int k){
        int length = arr.length;

        k = k % length;

        reverse(arr, 0, k - 1);
        reverse(arr, k, arr.length - 1);
        reverse(arr, 0, arr.length - 1);

        for(String str : arr){
            System.out.print(str);
        }
        System.out.println();
    }


    private static void reverse(String[] arr, int from, int to){
        String tmp;
        while(from < to){
            tmp = arr[from];
            arr[from++] = arr[to];
            arr[to--] = tmp;
        }
    }
}
